Лема за разрастване за безконтекстните езици. Ако един безкраен език L над азбуката S е безконтекстен, то всички думи от този език с изключение само на краен брой измежду тях допускат вариране от втори вид в L.

     За доказателството на горното твърдение ще въведем някои помощни понятия и ще докажем две предварителни леми.

     Нека G=(N,S,P) е безконтекстна нескъсяваща граматика над S. Ако Z е символ от N, а z е дума над S, то ще наричаме регулярен път в G от Z към z всяка крайна редица от думи от множеството S^*ґ N ґ S^*, която има начален член Z и удовлетворява условията: а) всеки неин член след началния (ако редицата има повече от един член) е изводим в G от предхождащия го и има по-голяма дължина от него; б) думата z е изводима в G от последния член на редицата.

     Ако съществува регулярен път в G от символа Z към думата z от S^*, то очевидно z е изводима от Z в G. Обратното е вярно по тривиална причина - ако z е изводима от Z в G, то едночленната редица с единствен член Z представлява регулярен път в G от Z към z. Могат да се дадат обаче и по-интересни примери.

     Пример 1. Нека S={a,f}, N={T}, S=T, P={T®a, T®fTT} (от гледна точка на математическата логика езикът на така дефинираната граматика G се състои от термовете, образувани с помощта само на константа a и на двуместен функционален символ f, но при запис с пропуснати скоби). Тогава думата fafaa е изводима от T в G и освен едночленната редица с единствен член T още следните редици са регулярни пътища в G от T към въпросната дума: (T,fTfaa), (T,faT), (T,fafTa), (T,fafaT), (T,faT,fafTa), (T,faT,fafaT).

     Следната лема хвърля светлина върху връзката между регулярните пътища и варируемостта от втори вид.

     Достатъчно условие за варируемост от втори вид. Нека G=(N,S,P) е безконтекстна граматика над S и нека броят на символите в множеството N е n. Ако съществува n+1-членен регулярен път в G от S към дадена дума z от S^*, то думата z допуска вариране от втори вид в езика на G.

     Доказателство. Нека z е дума от S^* и нека е налице някой n+1-членен регулярен път в G от S към z. Той ще има вида (u₁V₁w₁, ..., u_n+1V_n+1w_n+1), където V₁, ..., V_n+1 са символи от N, а u₁, ..., u_n+1, w₁, ..., w_n+1 са думи от S^*. В редицата (V₁,...,V_n+1) ще има някои два съвпадащи члена с различни номера. Нека имаме V_i=V_j, където 1 ≤ i < j ≤ n+1. Тъй като думата u_jV_jw_j е изводима в G от думата u_iV_iw_i, мултипликативното свойство на изводимостта в G позволява да заключим, че u_jV_jw_j = u_isw_i, където s е дума, изводима в G от символа V_i. При това думата s е с дължина, по-голяма от 1, поради неравенството |u_jV_jw_j| > |u_iV_iw_i|. Понеже думата u_i не съдържа буквата V_j, ясно е, че дължината на u_i не надминава дължината на u_j и следователно u_j=u_ix за някоя дума x от S^*. Аналогично виждаме, че w_j=yw_i за някоя дума y от S^*. Следователно имаме равенството u_ixV_jyw_i = u_isw_i. От него следва, че s=xV_jy=xV_iy и значи някоя от думите x и y не е празна. Като използваме равенството s=xV_iy и изводимостта на s от V_i в G, доказваме индуктивно, че думата x^rV_iy^r е изводима в G от V_i за всяко неотрицателно цяло число r. Сега ще използваме още и обстоятелството, че думата z е изводима в G от думата u_jV_jw_j, която е всъщност думата u_jV_iw_j. От него пак с помощта на мултипликативното свойство на изводимостта в G следва, че z=u_jvw_j, където v е някоя дума от S^*, изводима в G от V_i. Като заместим u_j и w_j с получените преди малко изрази за тях, стигаме до равенството z=u_ixvyw_i. При това за всяко неотрицателно цяло число r думата u_ix^rvy^rw_i принадлежи на езика на G, защото е от S^* и е изводима в G от думата u_ix^rV_iy^rw_i, която пък от своя страна е изводима от изводимата от S дума u_iV_iw_i. С това показахме, че думата z допуска вариране от втори вид в езика на G (ролята на u и w от дефиницията за варируемост от втори вид играят съответно u_i и w_i).

     Пример 2. Нека G е граматиката от пример 1. Тогава всяка дума от езика на G с изключение на еднобуквената дума a е изводима в G от думата fTT и следователно има вида fz₁z₂, където z₁ и z₂ също принадлежат на разглеждания език. При това положение например двучленната редица (T,fTz₂) ще представлява регулярен път от T към разглежданата дума. Оттук и от доказаната по-горе лема става ясно, че всички думи от езика на G, различни от еднобуквената дума a, допускат вариране от втори вид в споменатия език.

     Връщайки се отново към случая, когато G=(N,S,P) е произволна безконтекстна граматика над S, за всяко неотрицателно цяло число m и всеки символ Z от N да означим с K_m,Z множеството на онези думи от S^*, изводими от Z в G, към които в G няма регулярен m+1-членен път от Z. За всяко дадено неотрицателно цяло число m нека K_m да бъде обединението на множествата  K_m,Z , отговарящи на отделните символи Z от N.

     Пример 3. Ако G е граматиката, за която става дума в предходните два примера, то K₀ = Ж,  K₁ = K_1,T = {a},  K₂ = K_2,T = {a,faa}.

     Едно правило на граматиката G се нарича преименуващо, ако не само лявата му страна, но и дясната е символ от N (разбира се в конкретната граматика от разгледаните примери няма такива правила).

     Рекурентна лема за множествата K_m. Нека m е произволно неотрицателно цяло число, а z е дума от множеството K_m+1 . Тогава z е дясна страна на правило от P или може да се получи от някоя дясна страна на непреименуващо правило от P чрез заместване на участващите в нея символи от N с думи от множеството K_m .

     Доказателство. Нека Z е такъв символ от N, че  zОK_m+1,Z . Понеже думата z е изводима от Z в G и не е символ от N, тя е изводима от някоя изводима от Z дясна страна на непреименуващо правило от P. Ако въпросната дясна страна принадлежи на S^*, то z ще съвпада с нея. Ако пък тази дясна страна не принадлежи на S^*, тя ще има вида t₀Z₁t₁...t_k-1Z_kt_k , където k ≥ 1, Z₁, ..., Z_k са символи от N, а t₀, t₁, ..., t_k-1, t_k принадлежат на S^*. От мултипликативното свойство на изводимостта в G следва, че z = t₀z₁t₁...t_k-1z_kt_k , където z₁, ..., z_k са думи от S^*, изводими в G съответно от Z₁, ..., Z_k. Нека i е произволно измежду числата 1, ..., k. Да допуснем, че съществува регулярен път в G от Z_i към z_i, който е с m+1 члена, и да разгледаме един такъв път (s₁,...,s_m+1). Да положим

     Следствие. За всяко неотрицателно цяло число m съответното множество K_m е крайно.

     Доказателство. Ще използваме индукция относно m. При m = 0 твърдението е вярно - имаме K_0,Z = Ж за всеки символ Z от N, тъй като от Z към всяка дума от S^*, изводима от Z в G, съществува едночленен регулярен път в G. Да предположим сега, че за дадено неотрицателно цяло число m множеството K_m е крайно. Тъй като десните страни на правилата от P са крайно много, това предположение заедно с доказаната лема гарантира, че и множеството K_m+1 е крайно.

     Сега вече е лесно да се убедим във верността на изказаната в началото лема за разрастване за безконтекстните езици. Нека L е безконтекстен език над азбуката S^*, който е безкраен, и нека множеството на непразните думи от L се поражда от безконтекстната граматика G=(N,S,P). Да означим с n броя на символите от множеството N. Съгласно току-що доказаното следствие множеството K_n е крайно. Да разгледаме произволна дума z от L, непринадлежаща на множеството K_nИ{e}. Тя ще бъде дума от езика на G, непринадлежаща на K_n , а следователно и на K_n,S . Оттук следва, че съществува n+1-членен регулярен път в G от S към z. Благодарение на достатъчното условие за варируемост от втори вид това гарантира, че думата z допуска вариране от втори вид в езика на G, а значи и в езика L. По този начин доказахме, че всички думи от езика L допускат вариране в него с евентуално изключение само на такива измежду тях, които принадлежат на крайното множество K_nИ{e}.

  Последно изменение: 25.01.2003 г.